class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for(int j = n - 1; j >= 3; j--)
        {
            // 优化
            if(long(nums[0] + nums[1]) + long(nums[2] + nums[j]) > target) continue;
            if(long(nums[j] + nums[j - 1]) + long(nums[j - 2] + nums[j - 3]) < target) continue;

            // 跳过重复数字
            if(j + 1 < n && nums[j] == nums[j + 1]) continue;

            // 因为是四数之和，所以先固定一个数，接下去的就是处理三数之和的逻辑
            long long tmp = target - nums[j];

            for(int i = j - 1; i >= 2; i--)
            {
                // 优化
                if(long(nums[0] + nums[1]) + nums[i] > tmp) continue;
                if(long(nums[i - 2] + nums[i - 1]) + nums[i] < tmp) continue;

                // 跳过重复数字
                if(i + 1 < j && nums[i] == nums[i + 1]) continue;

                // 下面就是查找三数之和的主要逻辑
                int l = 0, r = i - 1;
                while(l < r)
                {
                    long long sum = long(nums[l] + nums[r]) + nums[i];
                    if(sum > tmp)
                        while(--r > l && nums[r + 1] == nums[r]);   // 跳过重复数字
                    else if(sum < tmp)
                        while(++l < r && nums[l - 1] == nums[l]);   // 跳过重复数字
                    else
                    {
                        ans.push_back({nums[l], nums[r], nums[i], nums[j]});
                        // 收集结果之后也要跳过重复数字
                        while(--r > l && nums[r + 1] == nums[r]);
                        while(++l < r && nums[l - 1] == nums[l]);
                    }
                }
            }
        }
        return ans;
    }
};